#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct element{
    char * data;
    struct element * prev;
    struct element * next;
};
struct element * create_element(char * data){
    struct element * elem=(struct element *)malloc(sizeof(struct element));
    int data_len=strlen(data);
    elem->data=(char *)malloc((data_len+1)*sizeof(char));
    strcpy(elem->data,data);
    elem->next=NULL;
    elem->prev=NULL;
    return elem;
}
void print_element(struct element * elem){
    printf("data:%s \t prev:%p \t next:%p \n",elem->data,elem->prev,elem->next);
}

struct double_linked_list{
    struct element * head;
    struct element * tail;
};

struct double_linked_list * create_double_linked_list(struct element * elem){
    if (elem!=NULL&&elem->data!=NULL){
        struct double_linked_list * lst=(struct double_linked_list *)malloc(sizeof(struct double_linked_list));
        lst->head=elem;
        lst->tail=elem;
        lst->head->next=lst->tail;
        lst->tail->prev=lst->head;
        return lst;
    }else{
        return NULL;
    }
    
}

void append_tail_double_linked_list(struct double_linked_list * lst,struct element * elem){
    lst->tail->next=elem;
    elem->prev=lst->tail;
    lst->tail=elem;
    lst->tail->next=lst->head;
    lst->head->prev=lst->tail;
}
void append_head_double_linked_list(struct double_linked_list * lst,struct element * elem){
    lst->head->prev=elem;
    elem->next=lst->head;
    lst->head=elem;
    lst->head->prev=lst->tail;
    lst->tail->next=lst->head;
}
void print_list(struct double_linked_list * lst){
    if(lst==NULL) return ;
    if(lst->head==NULL) return;
    struct element * current=lst->head;
    struct element * next=NULL;
    do{
        print_element(current);
        current=current->next;
    }while(current!=lst->head);
}

void insert_double_linked_list(struct double_linked_list * lst,int index,struct element * elem){
    if(lst==NULL) return;
    if(lst->head==NULL) return;
    if(index==0) {
        append_head_double_linked_list(lst,elem);
        return ;
    }else{
        int i=0;
        struct element * current=lst->head;
        int status=0;
        while(current->next!=lst->head){
            current=current->next;
            i++;
            if((index-1)==i) {
                status=1;
                break;
            }
        }
        if(status==1){
            struct element * prev=current;
            struct element * next=current->next;
            elem->next=next;
            next->prev=elem;

            elem->prev=prev;
            prev->next=elem;

        }else{
            printf("index out of range\n");
            return ;
        }
    }
}

int main(){
    char data[20]={0};
    scanf("%s",data);
    struct element * head=create_element(data);
    print_element(head);
    struct double_linked_list * lst=create_double_linked_list(head);
    for(int i=0;i<4;i++){
        scanf("%s",data);
        struct element * elem=create_element(data);
        print_element(elem);
        append_head_double_linked_list(lst,elem);
    }
    print_list(lst);
    struct element * elem=create_element(data);
    print_element(elem);    
    insert_double_linked_list(lst,6,elem);
    print_list(lst);
    return 0;
}